package com.gupao.alg.alg64;

import java.util.Arrays;

/**
 * 实现这三个方法
 * uniquePathsByRecursion()
 * uniquePaths2DimensionArray()
 * uniquePathsByDpArray()
 */
public class Topic_2_2_FindPaths {
    public static void main(String[] args) {
        int m = 3, n = 3;
        System.out.println("通过递归实现：");
        System.out.println(uniquePathsByRecursion(m, n));

        System.out.println("通过二维数组实现：");
        System.out.println(uniquePaths2DimensionArray(m, n));

        System.out.println("通过动态数组实现：");
        System.out.println(uniquePathsByDpArray(m, n));
    }

    /**
     * 方法1 通过递归方式实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePathsByRecursion(int m, int n) {
        return search(m, n);

    }

    public static int search(int m, int n) {
        //0 1 1
        //1 1 1
        //1 1 2
        if (m == 1 || n == 1) {
             return  1;
        }
        return search(m, n - 1) + search(m - 1, n);
    }

    /**
     * 通过二维数组实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths2DimensionArray(int m, int n) {
        //1 1 1
        //1 2 3
        //1 3 6
        int[][] temp = new int[m][n];
        for(int i =0 ; i < m ; i++){
            temp[i][0] = 1;
        }
        for (int j = 0 ;j < n ; j++){
            temp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                temp[i][j] = temp[i-1][j] + temp[i][j-1];
            }
        }
        return temp[m-1][n-1];
    }

    /**
     * 通过动态数组实现
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePathsByDpArray(int m, int n) {
        //1 1 1   row
        //1 2 3
        //1 3 6
        int[] temp =new int[n];
        Arrays.fill(temp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                temp[j]  = temp[j] + temp[j-1];
            }
        }
        return temp[n-1];
    }
}
